import copy

grammar3 = {
    "terminals": {"+", "*","^", "i", "(", ")"},
    "non_terminals": {"E", "T", "F", "P"},
    "start": "E",
    "productions": [
        ("E", ["E", "+", "T"]),     # E→T+E'
        ("E", ["T"]),               # E→T
        ("T", ["T", "*", "F"]),     # T=T*F
        ("T", ["F"]),               # T→F
        ("F", ["P", "^", "F"]),     # F→P^F  乘方
        ("F", ["P"]),               # F→P
        ("P", ["(", "E", ")"]),     # P→(E)  括号
        ("P", ["i"]),               # P→i
    ],
}

#计算FIRSTVT集合
def FIRSTVT(grammar):
    non_terminals = grammar["non_terminals"]
    productions = grammar["productions"]
    firstvt = {}
    for nt in non_terminals:
        firstvt[nt] = set()
    changed = True # 初始化changed为True
    last_firstvt = set()
    while changed:
        for prod in productions:
            left, right = prod
            if len(right) == 0:
                continue
            if right[0] in non_terminals: # 如果右部第一个符号是非终结符
                if len(right) > 1 and right[1] not in non_terminals:
                    firstvt[left].update([right[1]])
                firstvt[left].update(firstvt[right[0]]) #
            if right[0] not in non_terminals:# 如果右部第一个符号是终结符
                firstvt[left].add(right[0])
        if firstvt == last_firstvt:
            changed = False
        last_firstvt = copy.deepcopy(firstvt)

    return firstvt

#计算LASTVT集合
def LASTVT(grammar):
    non_terminals = grammar["non_terminals"]
    productions = grammar["productions"]
    lastvt = {}
    for nt in non_terminals:
        lastvt[nt] = set()
    changed = True
    last_lastvt = set()
    while changed:
        for prod in reversed(productions):
            left, right = prod
            cnt =len(right)
            for i in range(0,cnt,1):
                if right[-1] not in non_terminals: # 如果右部最后一个符号是终结符
                    lastvt[left].update([right[-1]])
                if right[-1] in non_terminals: # 如果右部最后一个符号是非终结符
                    if cnt>1:
                        lastvt[left].update([right[-2]])
                    lastvt[left].update(lastvt[right[-1]])
        if lastvt == last_lastvt:
            changed = False
        last_lastvt = copy.deepcopy(lastvt)
    return lastvt

    
if __name__ == '__main__':
    print(f"FIRSTVT:\n{FIRSTVT(grammar3)}")
    print(f"LASTVT:\n{LASTVT(grammar3)}")